import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

public class demo2 {
    public int ladderLength(String beginWord, String endWord, List<String> wordList) {
        if(beginWord.equals(endWord))return 1;
        if(!wordList.contains(endWord))return 0;
        int n=beginWord.length();
        //使用哈希表来提高效率
        HashSet<String>set=new HashSet();
        for(String tt:wordList){
            set.add(tt);
        }
        Queue<String> queue=new LinkedList<>();
        HashSet<String> hashSet=new HashSet<>();
        int sum=0;
        queue.add(beginWord);
        while (!queue.isEmpty()){
            int size=queue.size();
            sum++;
            while (size-->0){
                String t=queue.poll();
                for(int i=0;i<n;i++){
                    char[] arr = t.toCharArray();
                    char s='a';
                    for (int j = 0; j <26 ; j++) {
                        char temp= (char) (s+j);
                        arr[i]=temp;
                        String ss=new String(arr);
                        if(!hashSet.contains(ss)&&set.contains(ss)){
                            if(endWord.equals(ss))return sum+1;
                            queue.add(ss);
                            hashSet.add(ss);
                        }
                    }

                }
            }
        }
        return 0;
    }
}
